home *** CD-ROM | disk | FTP | other *** search
/ STraTOS 1997 April & May / STraTOS 1 - 1997 April & May.iso / CD01 / INTERNET / SITES / RAND / BM132A.LZH / bm_132a / bspd.s < prev    next >
Encoding:
Text File  |  1995-11-28  |  30.1 KB  |  980 lines
  1. *=======================================================*
  2. *    BSP-Descent: latest update 27/11/95        *
  3. *=======================================================*
  4. *    Descend BSP tree, generating sectors & walls.    *
  5. *=======================================================*
  6. *     >    New 68030 replacement by Douglas Little.    *
  7. *     >    Atari C conversion by Johan Klockars.        *
  8. *     >    Original C++ code for the PC by Jake Hill.    *
  9. *=======================================================*
  10. *    Some improvements made to 68030 version:    *
  11. *=======================================================*
  12. *     >    Node-quadrant checks changed to octants.    *
  13. *     >    Nodes projected & checked against viewcone.     *
  14. *     >    Nodes checked against wall occlusion list.    *
  15. *     >    Program recursion removed & replaced by stack.    *
  16. *     >    Optimised for latent-memory references.        *
  17. *     >    Accuracy of 3D calculations improved (32 bit).    *
  18. *     >    Local variables accessed from structure.    *
  19. *     >    Temporary lighting effects just for fun.    *
  20. *     >    Several 16-bit offset-addressing bug fixes.    *
  21. *     >    Logic flow simplified around AddWall        *
  22. *     >    Projection now peformed in realtime.        *
  23. *=======================================================*
  24.  
  25. invisible_code    =    0
  26. visible_code    =    1
  27.  
  28. *~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
  29. *    Descend Binary Space Partitioning Tree        *
  30. *~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
  31. descend_bsp:
  32. *-------------------------------------------------------*
  33. *    Place start & terminator on heap and descend    *
  34. *-------------------------------------------------------*
  35.     move.l        sp,bsp_return
  36.     lea        display_struct,a6
  37.     push.w        #terminator
  38.     push.w        maxnode
  39.     bra        next_node
  40. *-------------------------------------------------------*
  41. *    Thread returns here when tree is exhausted    *
  42. *-------------------------------------------------------*
  43. finish_tree:
  44. *-------------------------------------------------------*
  45.     move.l        bsp_return,sp
  46.     rts
  47.  
  48. *~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
  49. *    [node] = [sector] -> draw this node        *
  50. *~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
  51. ssector_node:
  52. *-------------------------------------------------------*
  53. *    Stop drawing when [width] columns are filled    *
  54. *-------------------------------------------------------*
  55.     tst.w        columns
  56.     beq.s        finish_tree
  57. *-------------------------------------------------------*
  58. *    Stop drawing when last node has been popped    *
  59. *-------------------------------------------------------*
  60.     not.w        d0
  61.     beq.s        finish_tree
  62.     eor.w        #$7FFF,d0
  63.  
  64. *~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
  65. *    Render ssector into run-buffer            *
  66. *~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
  67. build_ssector:
  68. *-------------------------------------------------------*
  69. *    Locate [segs] for this [ssector]        *
  70. *-------------------------------------------------------*
  71.     move.l        display_ssectors(a6),a0
  72.     moveq        #0,d4
  73.     move.w        ssec_first(a0,d0.w*4),d4
  74.     moveq        #0,d3
  75.     move.w        ssec_segments(a0,d0.w*4),d3
  76. *-------------------------------------------------------*
  77. *    Locate [linedef] & [sidedef] for first [seg]    *
  78. *-------------------------------------------------------*
  79.     move.l        d4,d0
  80.     move.l        display_segs(a6),a2
  81.     add.l        d0,d0
  82.     add.l        d4,d0
  83.     lsl.l        #2,d0
  84.     add.l        d0,a2                ; a+(d*12)
  85.     moveq        #0,d0
  86.     move.w        seg_linedef(a2),d0
  87.     moveq        #0,d2
  88.     move.w        seg_sidedef(a2),d2
  89. *-------------------------------------------------------*
  90. *    Locate right [sidedef] for this [linedef]    *
  91. *-------------------------------------------------------*
  92.     move.l        d0,d1
  93.     move.l        display_linedefs(a6),a0
  94.     lsl.l        #3,d0
  95.     sub.l        d1,d0
  96.     add.l        d0,d0
  97.     add.l        d0,a0                ; a+(d*14)
  98.     moveq        #0,d1
  99.     move.w        linedef_right(a0,d2.w*2),d1 
  100. *-------------------------------------------------------*
  101. *    Locate [sector] for this [sidedef]        *
  102. *-------------------------------------------------------*
  103.     move.l        d1,d0 
  104.     move.l        display_sidedefs(a6),a0
  105.     lsl.l        #4,d0 
  106.     sub.l        d1,d0                ; a+(d*30)
  107.     move.w        sidedef_sector(a0,d0.l*2),d1    
  108. *-------------------------------------------------------*
  109. *    Set up floor & ceiling heights for this sector    *
  110. *-------------------------------------------------------*
  111.     move.l        d1,d0
  112.     add.l        d0,d0
  113.     move.l        d0,d2
  114.     lsl.l        #3,d0
  115.     move.l        display_sectors(a6),a0
  116.     sub.l        d2,d0
  117.     sub.l        d1,d0                ; a+(d*26)
  118.     add.l        d0,d0
  119.     add.l        d0,a0
  120.     move.l        a0,this_sector
  121.     move.w        sector_floorht(a0),floor_ht
  122.     move.w        sector_ceilht(a0),ceiling_ht
  123. *-------------------------------------------------------*
  124. *    Are we in this sector?                *
  125. *-------------------------------------------------------*
  126.     tst.w        first_ssector
  127.     beq.s        .skip
  128.     clr.w        first_ssector
  129. *-------------------------------------------------------*
  130. *    Set viewcone to (sector_height+player_height)    *
  131. *-------------------------------------------------------*
  132.     move.w        floor_ht,d0
  133.     add.w        #player_height,d0
  134.     move.w        d0,Ph
  135. *-------------------------------------------------------*
  136. *    Set up segment-heap for loop            *
  137. *-------------------------------------------------------*
  138. .skip:    move.l        d4,d2
  139.     move.w        d2,display_segbase(a6)
  140.     move.w        d3,display_segnum(a6)
  141.     ble        end_ssector
  142. *-------------------------------------------------------*
  143. *    Process simple lighting effects (temporary!)    *
  144. *-------------------------------------------------------*
  145.     ifd        lighting_effects
  146.     bsr        process_lighting
  147.     endc
  148. *~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
  149. *    Render segments surrounding this ssector    *
  150. *~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
  151. segment_loop:
  152. *~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
  153. *    Hidden surface removal stage #1            *
  154. *~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
  155. *    Is viewer on left or right side of this line?    *
  156. *-------------------------------------------------------*
  157. *    ((y2-y1)*(Px-x1))) => (((x2-x1)*(Py-y1)) ?    *
  158. *-------------------------------------------------------*
  159.     move.l        display_vertices(a6),a0
  160.     moveq        #0,d0
  161.     moveq        #0,d1
  162.     move.w        linedef_from(a2),d0
  163.     move.w        linedef_to(a2),d1
  164.     move.w        vtx_x(a0,d0.l*4),d5
  165.     move.w        vtx_x(a0,d1.l*4),d6
  166.     move.w        vtx_y(a0,d0.l*4),d0
  167.     move.w        vtx_y(a0,d1.l*4),d1
  168.     sub.w        d5,d6            ; x2-x1
  169.     sub.w        d0,d1            ; y2-y1
  170.     neg.w        d5
  171.     add.w        display_px(a6),d5    ; px-x1
  172.     neg.w        d0
  173.     add.w        display_py(a6),d0    ; py-y1
  174.     muls.w        d6,d0            ; (x2-x1)*(Py-y1)
  175.     muls.w        d5,d1            ; (y2-y1)*(Px-x1)
  176.     cmp.l        d0,d1
  177.     bmi        invisible
  178. *~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
  179. *    Segment is visible                *
  180. *~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
  181.     pea        (a2)
  182. *-------------------------------------------------------*
  183.     moveq        #0,d0
  184.     move.w        display_segbase(a6),d0
  185.     move.l        d0,d1
  186.     move.l        display_segs(a6),a5
  187.     add.l        d0,d0
  188.     add.l        d1,d0
  189.     lsl.l        #2,d0
  190.     add.l        d0,a5            ; a+(d*12)
  191. *-------------------------------------------------------*
  192. *    Locate segment vertices                *
  193. *-------------------------------------------------------*
  194.     move.l        display_vertices(a6),a0
  195.     moveq        #0,d0
  196.     move.w        seg_from(a5),d0
  197.     move.l        a0,a1
  198.     moveq        #0,d1
  199.     move.w        seg_to(a5),d1 
  200.     lsl.l        #2,d0
  201.     lsl.l        #2,d1
  202.     add.l        d0,a0            ; a+(d*4)
  203.     add.l        d1,a1            ; a+(d*4)
  204. *-------------------------------------------------------*
  205. *    Fetch X1,Y1 / X2,Y2 & centre around viewpoint    *
  206. *-------------------------------------------------------*
  207.     move.w        display_px(a6),d1
  208.     move.w        display_py(a6),d7
  209.     move.w        vtx_x(a0),d4
  210.     move.w        vtx_y(a0),d5
  211.     move.w        vtx_x(a1),d6
  212.     move.w        vtx_y(a1),d2
  213.     sub.w        d1,d4        ; dx1
  214.     sub.w        d7,d5        ; dy1
  215.     sub.w        d1,d6        ; dx2
  216.     sub.w        d7,d2        ; dy2
  217. *-------------------------------------------------------*
  218. *    Rotate X & Y into canonical VX & VZ        *
  219. *-------------------------------------------------------*
  220.     move.w        display_sina(a6),d0
  221.     move.w        display_cosa(a6),d7
  222. *-------------------------------------------------------*
  223. *    x1 = (dx1)*sin(a) + (dy1)*cos(a)        *
  224. *    z1 = (dx1)*cos(a) - (dy1)*sin(a)        *
  225. *-------------------------------------------------------*
  226.     move.w        d4,d3
  227.     move.w        d5,d1
  228.     muls.w        d7,d4
  229.     muls.w        d0,d5
  230.     muls.w        d0,d3
  231.     muls.w        d7,d1
  232.     sub.l        d5,d4
  233.     add.l        d1,d3
  234. *-------------------------------------------------------*
  235. *    x2 = (dx2)*sin(a) + (dy2)*cos(a)        *
  236. *    z2 = (dx2)*cos(a) - (dy2)*sin(a)        *
  237. *-------------------------------------------------------*
  238.     move.w        d6,d5
  239.     move.w        d2,d1
  240.     muls.w        d7,d6
  241.     muls.w        d0,d2
  242.     muls.w        d0,d5
  243.     muls.w        d7,d1
  244.     sub.l        d2,d6
  245.     add.l        d1,d5
  246. *-------------------------------------------------------*
  247. *    Renormalize output from matrix            *
  248. *-------------------------------------------------------*
  249.     lsl.l        #2,d3        ; x1
  250.     lsl.l        #2,d4        ; z1
  251.     lsl.l        #2,d5        ; x2
  252.     lsl.l        #2,d6        ; z2
  253. *~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
  254. *    Z-clipping of walls                *
  255. *~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
  256.     moveq        #ZMIN,d0
  257.     swap        d0
  258. *-------------------------------------------------------*
  259. *    Check for intersection with viewplane        *
  260. *-------------------------------------------------------*
  261.     cmp.l        d0,d4
  262.     bgt.s        .vis1
  263. *-------------------------------------------------------*
  264. *    Skip segment if both points are behind viewer    *
  265. *-------------------------------------------------------*
  266.     cmp.l        d0,d6
  267.     ble        end_segment
  268. *-------------------------------------------------------*
  269. *    Case #1 - clip X1,Z1 against ZMIN        *
  270. *-------------------------------------------------------*
  271.     sub.l        d4,d0        ; (cz-z1)
  272.     move.l        d5,d1
  273.     sub.l        d3,d1        ; (x2-x1)
  274.     muls.l        d0,d2:d1    ; (x2-x1)*(cz-z1)
  275.     move.l        d6,d0
  276.     sub.l        d4,d0        ; (z2-z1)
  277.     divs.l        d0,d2:d1    ; ((x2-x1)*(cz-z1))/(z2-z1)
  278.     add.l        d1,d3        ; (((x2-x1)*(cz-z1))/(z2-z1))+x1
  279.     moveq        #ZMIN,d4
  280.     swap        d4        ; z1 = cz
  281.     bra.s        .vis2
  282. *-------------------------------------------------------*
  283. *    Draw segment if both points are in view        *
  284. *-------------------------------------------------------*
  285. .vis1:    cmp.l        d0,d6
  286.     bgt.s        .vis2
  287. *-------------------------------------------------------*
  288. *    Case #2 - clip X2,Z2 against ZMIN        *
  289. *-------------------------------------------------------*
  290.     sub.l        d6,d0        ; (cz-z2)
  291.     move.l        d3,d1
  292.     sub.l        d5,d1        ; (x1-x2)
  293.     muls.l        d0,d2:d1    ; (x1-x2)*(cz-z2)
  294.     move.l        d4,d0
  295.     sub.l        d6,d0        ; (z1-z2)
  296.     divs.l        d0,d2:d1    ; ((x1-x2)*(cz-z2))/(z1-z2)
  297.     add.l        d1,d5        ; (((x1-x2)*(cz-z2))/(z1-z2))+x2
  298.     moveq        #ZMIN,d6
  299.     swap        d6        ; z2 = cz
  300. *-------------------------------------------------------*
  301. *    Project points into 2D viewspace        *
  302. *-------------------------------------------------------*
  303. .vis2:    moveq        #0,d1
  304.     move.w        display_shwid(a6),d1
  305.     swap        d1
  306.     muls.l        d1,d0:d3
  307.     divs.l        d4,d0:d3
  308.     muls.l        d1,d0:d5
  309.     divs.l        d6,d0:d5
  310.     move.l        d1,d0
  311.     add.l        d0,d0
  312. *-------------------------------------------------------*
  313. *    Centre screen coordinates & check bounds    *
  314. *-------------------------------------------------------*
  315.     neg.l        d5
  316.     add.l        d1,d5
  317.     ble        end_segment
  318.     move.l        d5,d7
  319.     cmp.l        d0,d7
  320.     bmi.s        .i2in
  321.     move.l        d0,d7    
  322. .i2in:    neg.l        d3
  323.     add.l        d1,d3
  324.     move.l        d3,d1
  325.     bpl.s        .i1in
  326.     moveq        #0,d1
  327. .i1in:    cmp.l        d0,d3
  328.     bpl        end_segment
  329. *-------------------------------------------------------*
  330. *    Check size (i2-i1)                *
  331. *-------------------------------------------------------*
  332.     swap        d1
  333.     swap        d7
  334.     move.w        d7,d0
  335.     sub.w        d1,d0
  336.     ble        end_segment
  337. *-------------------------------------------------------*
  338. *    Discard fully occluded walls            *
  339. *-------------------------------------------------------*
  340.     ifd        dsp
  341. *-------------------------------------------------------*
  342.     dspwrite.l    #scan_command
  343.     ext.l        d1
  344.     dspwrite.l    d1
  345.     ext.l        d7
  346.     dspwrite.l    d7
  347.     dspread.w    d0
  348.     cmp.w        #visible_code,d0
  349.     bne        end_segment
  350. *-------------------------------------------------------*
  351.     elseif
  352. *-------------------------------------------------------*
  353.     lea        occlusion_list,a2
  354.     add.w        d1,a2
  355.     moveq        #4-1,d2
  356.     and.w        d0,d2
  357.     lsr.w        #2,d0
  358.     bra.s        .sbs
  359. .sb:    tst.b        (a2)+
  360.     bne.s        .draw
  361. .sbs:    dbra        d2,.sb
  362.     bra.s        .sls
  363. .sl:    tst.l        (a2)+
  364.     bne.s        .draw
  365. .sls:    dbra        d0,.sl
  366.     bra        end_segment
  367. *-------------------------------------------------------*
  368.     endc
  369. *-------------------------------------------------------*
  370. *    Write coordinates into addwall struct        *
  371. *-------------------------------------------------------*
  372. .draw:    lea        addwall_struct,a2
  373.     move.l        d3,addwall_i1(a2)
  374.     move.l        d4,addwall_z1(a2)
  375.     move.l        d5,addwall_i2(a2)
  376.     move.l        d6,addwall_z2(a2)
  377. *-------------------------------------------------------*
  378. *    Look up linedef for this seg            *
  379. *-------------------------------------------------------*
  380.     moveq        #0,d1
  381.     move.w        seg_linedef(a5),d1
  382.     move.l        d1,d0 
  383.     move.l        display_linedefs(a6),a0
  384.     lsl.l        #3,d0 
  385.     sub.l        d1,d0
  386.     add.l        d0,d0
  387.     add.l        d0,a0
  388.     move.l        a0,a1
  389. *-------------------------------------------------------*
  390. *    Determine one or two-sided linedef        *
  391. *-------------------------------------------------------*
  392.     moveq        #attrib_twosided,d0
  393.     and.w        linedef_attrib(a0),d0
  394.     move.b        d0,twosided_flag
  395. *-------------------------------------------------------*
  396. *    Determine which sidedef is facing us        *
  397. *-------------------------------------------------------*
  398.     move.w        seg_sidedef(a5),d0
  399.     moveq        #0,d5
  400.     move.w        linedef_right(a0,d0.l*2),d5    ; visible sidedef
  401.     bchg        #0,d0
  402.     moveq        #0,d6
  403.     move.w        linedef_right(a0,d0.l*2),d6    ; invisible sidedef
  404. *-------------------------------------------------------*
  405. *    Look up sidedef for visible side of linedef    *
  406. *-------------------------------------------------------*
  407.     move.l        d5,d0
  408.     move.l        d0,d1
  409.     move.l        display_sidedefs(a6),a3
  410.     lsl.l        #4,d0
  411.     sub.l        d1,d0
  412.     add.l        d0,d0
  413.     add.l        d0,a3                ; a+(d*30)
  414. *-------------------------------------------------------*
  415. *    (a6) pointer to addwall structure        *
  416. *-------------------------------------------------------*
  417.     lea        addwall_struct,a6
  418. *-------------------------------------------------------*
  419. *    Hack colours & lighting to something useful    *
  420. *-------------------------------------------------------*
  421.     move.w        a3,sector_colour
  422.     move.w        sidedef_sector(a3),d0
  423.     bsr        select_colours
  424. *-------------------------------------------------------*
  425. *    Check for main wall texture            *
  426. *-------------------------------------------------------*
  427.     cmpi.b        #'-',sidedef_mtns(a3) 
  428.     beq.s        sector_window
  429. *-------------------------------------------------------*
  430. *    Valid texture indicates a solid sector wall    *
  431. *-------------------------------------------------------*
  432. sector_wall:    
  433. *-------------------------------------------------------*
  434.     move.b        twosided_flag,addwall_opaque(a6)
  435.     move.w        Ph,d0
  436.     move.w        d0,d1
  437.     sub.w        ceiling_ht,d1
  438.     move.w        d0,d2
  439.     sub.w        floor_ht,d2
  440.     cmp.w        d1,d2
  441.     bmi        end_segment
  442.     move.w        d1,addwall_y1(a6)
  443.     move.w        d2,addwall_y2(a6)
  444.     move.b        #WALL_TYPE,addwall_type(a6)
  445.     bsr        AddWall
  446.     bra        end_segment
  447. *-------------------------------------------------------*
  448. sector_window:
  449. *-------------------------------------------------------*
  450.     move.b        #0,addwall_opaque(a6)
  451. *-------------------------------------------------------*
  452. *    Locate [sector] on opposite side of [linedef]    *
  453. *-------------------------------------------------------*
  454.     move.l        d6,d0
  455.     move.l        Side_Array,a4
  456.     move.l        d0,d1
  457.     lsl.l        #4,d0
  458.     sub.l        d1,d0
  459.     move.w        sidedef_sector(a4,d0.l*2),a0    ; a+(d*30)
  460.     lea        (a0,a0.l*2),a2
  461.     move.l        Sector_Array,a1
  462.     move.l        a2,d0 
  463.     lsl.l        #2,d0
  464.     add.l        a0,d0
  465.     lea        (a1,d0.l*2),a4            ; a+(d*26)
  466. *-------------------------------------------------------*
  467. *    Check for lower wall texture            *
  468. *-------------------------------------------------------*
  469.     move.w        floor_ht,d1 
  470.     cmp.b        #'-',sidedef_ltns(a3) 
  471.     beq.s        lower_floor
  472. *-------------------------------------------------------*
  473. *    Valid texture indicates a solid lower wall    *
  474. *-------------------------------------------------------*
  475. lower_wall:
  476. *-------------------------------------------------------*
  477.     move.w        sector_floorht(a4),d1
  478.     cmp.w        ceiling_ht,d1
  479.     bmi.s        lower_floor
  480.     move.w        ceiling_ht,d1
  481. *-------------------------------------------------------*
  482. lower_floor:
  483. *-------------------------------------------------------*
  484.     move.w        floor_ht,d2 
  485.     neg.w        d1
  486.     neg.w        d2
  487.     add.w        Ph,d1
  488.     add.w        Ph,d2
  489.     cmp.w        d1,d2
  490.     bpl.s        .fix
  491.     move.w        d2,d1
  492. .fix:    move.w        d1,addwall_y1(a6)
  493.     move.w        d2,addwall_y2(a6)
  494.     move.b        #LOWER_TYPE,addwall_type(a6)
  495.     bsr        AddWall 
  496.     tst.w        columns
  497.     beq.s        end_segment         
  498. *-------------------------------------------------------*
  499. *    Check for upper wall texture            *
  500. *-------------------------------------------------------*
  501.     move.w        ceiling_ht,d2 
  502.     cmp.b        #'-',sidedef_utns(a3) 
  503.     beq.s        upper_ceiling
  504. *-------------------------------------------------------*
  505. *    Valid texture indicates a solid upper wall    *
  506. *-------------------------------------------------------*
  507. upper_wall:
  508. *-------------------------------------------------------*
  509.     move.w        sector_ceilht(a4),d2
  510.     cmp.w        floor_ht,d2
  511.     bpl.s        upper_ceiling
  512.     move.w        floor_ht,d2
  513. *-------------------------------------------------------*
  514. upper_ceiling:
  515. *-------------------------------------------------------*
  516.     move.w        ceiling_ht,d1 
  517.     neg.w        d1
  518.     neg.w        d2
  519.     add.w        Ph,d1
  520.     add.w        Ph,d2
  521.     cmp.w        d1,d2
  522.     bpl.s        .fix
  523.     move.w        d1,d2
  524. .fix:    move.w        d1,addwall_y1(a6)
  525.     move.w        d2,addwall_y2(a6)
  526.     move.b        #UPPER_TYPE,addwall_type(a6)
  527.     bsr        AddWall 
  528. *-------------------------------------------------------*
  529. end_segment:
  530. *-------------------------------------------------------*
  531.     pop.l        a2
  532. *-------------------------------------------------------*
  533. *    Proceed to next segment                *
  534. *-------------------------------------------------------*
  535. invisible:
  536. *-------------------------------------------------------*
  537.     lea        display_struct,a6
  538.     lea        seg_len(a2),a2
  539.     addq.w        #1,display_segbase(a6)
  540.     subq.w        #1,display_segnum(a6)
  541.     beq        end_ssector
  542.     tst.w        columns
  543.     bne        segment_loop
  544. *-------------------------------------------------------*
  545. end_ssector:
  546. *-------------------------------------------------------*
  547. *    Fetch next node from heap and descend again    *
  548. *-------------------------------------------------------*
  549. next_node:
  550. *-------------------------------------------------------*
  551.     move.w        (sp)+,d0
  552.     bmi        ssector_node
  553.  
  554. *~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
  555. *    [node] /= [sector] -> descend again        *
  556. *~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
  557. dividing_node:
  558. *-------------------------------------------------------*
  559.     move.l        display_nodes(a6),a1    
  560.     move.l        (a1,d0.w*4),a1
  561. *-------------------------------------------------------*
  562. *    Inverse descent rules for left side of tree    *
  563. *-------------------------------------------------------*
  564. *    (dy*(x1-Px))) => ((dx*(y1-Py)) ?        *
  565. *-------------------------------------------------------*
  566.     move.w        node_dx(a1),d2
  567.     move.w        node_x(a1),d0
  568.     move.w        node_dy(a1),d3
  569.     move.w        node_y(a1),d1
  570.     add.w        d2,d0            ; x2 = (x1+dx)
  571.     sub.w        display_px(a6),d0    ; (x2-px)
  572.     add.w        d3,d1            ; y2 = (y1+dy)
  573.     sub.w        display_py(a6),d1    ; (xy-py)
  574.     muls.w        d2,d1            ; (y2-py) * dx
  575.     muls.w        d3,d0            ; (x2-px) * dy
  576.     cmp.l        d0,d1 
  577.     bmi.s        node_leftside
  578. *-------------------------------------------------------*
  579. *    Viewer is on right side of node divider        *
  580. *-------------------------------------------------------*
  581. node_rightside:
  582. *-------------------------------------------------------*
  583.     lea        node_lvtx(a1),a0
  584.     bsr.s        nodeincone
  585.     beq.s        .noln
  586.     move.w        node_left(a1),-(sp)
  587. .noln:    lea        node_rvtx(a1),a0
  588.     bsr.s        nodeincone
  589.     beq.s        next_node
  590.     move.w        node_right(a1),-(sp) 
  591.     bra.s        next_node
  592. *-------------------------------------------------------*
  593. *    Viewer is on left side of node divider        *
  594. *-------------------------------------------------------*
  595. node_leftside:
  596. *-------------------------------------------------------*
  597.     lea        node_rvtx(a1),a0
  598.     bsr.s        nodeincone
  599.     beq.s        .noln
  600.     move.w        node_right(a1),-(sp) 
  601. .noln:    lea        node_lvtx(a1),a0
  602.     bsr.s        nodeincone
  603.     beq.s        next_node
  604.     move.w        node_left(a1),-(sp)
  605.     bra.s        next_node
  606.  
  607. *~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
  608. *    Determine visibility of a child node.        *
  609. *~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
  610. *    Only exposed nodes are dealt with.        *
  611. *~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
  612.  
  613. *-------------------------------------------------------*
  614. *    Check #1 -> Octal node elimination        * 
  615. *-------------------------------------------------------*
  616. *    All nodes are checked against the 3 octal    *
  617. *    segments immediately in front of viewcone.    *
  618. *    Nodes from 5 of all 8 octants are discarded.    *
  619. *-------------------------------------------------------*
  620. *    Check #2 -> Canonical volume intersection    * 
  621. *-------------------------------------------------------*
  622. *    The remaining nodes are fully intersected    *
  623. *    with the projected canonical view volume.    *
  624. *    Any nodes outside the viewcone are discarded.    *
  625. *-------------------------------------------------------*
  626. *    Check #3 -> Occlusion check            * 
  627. *-------------------------------------------------------*
  628. *    Any nodes remaining in view are checked        *
  629. *    against the occlusion table. Any nodes        *
  630. *    completely occluded by walls are discarded.    *
  631. *-------------------------------------------------------*
  632. nodeincone:
  633. *~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
  634. *    Octal segment BSP node eliminator        *
  635. *~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
  636. *    Eliminates nodes from 5 out of all 8 octants    *
  637. *~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
  638. qx1    equr        d1
  639. qy1    equr        d2
  640. qx2    equr        d3
  641. qy2    equr        d4
  642. *-------------------------------------------------------*
  643.     move.w        display_px(a6),d5
  644.     move.w        display_py(a6),d6
  645.     move.w        display_octant(a6),d7
  646.     moveq        #0,d0
  647.     jmp        octs(pc,d7.w)
  648. *-------------------------------------------------------*
  649. *    Octant elimination table             *
  650. *-------------------------------------------------------*
  651. *    Octants are out of phase by 1/4 turn        *
  652. *-------------------------------------------------------*
  653. octs:    dc.w        oct_2-octs
  654.     dc.w        oct_3-octs
  655.     dc.w        oct_4-octs
  656.     dc.w        oct_5-octs
  657.     dc.w        oct_6-octs
  658.     dc.w        oct_7-octs
  659.     dc.w        oct_0-octs
  660.     dc.w        oct_1-octs
  661. *-------------------------------------------------------*
  662. *    Octant elimination routines             *
  663. *-------------------------------------------------------*
  664. oct_0:    move.w        nodevtx_y1(a0),qy1
  665.     move.w        nodevtx_x2(a0),qx2
  666.     sub.w        d6,qy1
  667.     bpl.s        .x
  668.     sub.w        d5,qx2
  669.     cmp.w        qy1,qx2
  670.     bpl        project_node
  671. .x:    tst.l        d0
  672.     rts
  673. *-------------------------------------------------------*
  674. oct_1:    move.w        nodevtx_x2(a0),qx2
  675.     move.w        nodevtx_y1(a0),qy1
  676.     sub.w        d5,qx2
  677.     bmi.s        .x
  678.     sub.w        d6,qy1
  679.     cmp.w        qy1,qx2
  680.     bpl        project_node
  681. .x:    tst.l        d0
  682.     rts
  683. *-------------------------------------------------------*
  684. oct_2:    move.w        nodevtx_x2(a0),qx2
  685.     move.w        nodevtx_y2(a0),qy2
  686.     sub.w        d5,qx2
  687.     bmi.s        .x
  688.     sub.w        d6,qy2
  689.     neg.w        qy2
  690.     cmp.w        qy2,qx2
  691.     bpl.s        project_node
  692. .x:    tst.l        d0
  693.     rts
  694. *-------------------------------------------------------*
  695. oct_3:    move.w        nodevtx_y2(a0),qy2
  696.     move.w        nodevtx_x2(a0),qx2
  697.     sub.w        d6,qy2
  698.     bmi.s        .x
  699.     sub.w        d5,qx2
  700.     neg.w        qy2
  701.     cmp.w        qy2,qx2
  702.     bpl.s        project_node
  703. .x:    tst.l        d0
  704.     rts
  705. *-------------------------------------------------------*
  706. oct_4:    move.w        nodevtx_y2(a0),qy2
  707.     move.w        nodevtx_x1(a0),qx1
  708.     sub.w        d6,qy2
  709.     bmi.s        .x
  710.     sub.w        d5,qx1
  711.     cmp.w        qy2,qx1
  712.     bmi.s        project_node
  713. .x:    tst.l        d0
  714.     rts
  715. *-------------------------------------------------------*
  716. oct_5:    move.w        nodevtx_x1(a0),qx1
  717.     move.w        nodevtx_y2(a0),qy2
  718.     sub.w        d5,qx1
  719.     bpl.s        .x
  720.     sub.w        d6,qy2
  721.     cmp.w        qy2,qx1
  722.     bmi.s        project_node
  723. .x:    tst.l        d0
  724.     rts
  725. *-------------------------------------------------------*
  726. oct_6:    move.w        nodevtx_x1(a0),qx1
  727.     move.w        nodevtx_y1(a0),qy1
  728.     sub.w        d5,qx1
  729.     bpl.s        .x
  730.     sub.w        d6,qy1
  731.     neg.w        qy1
  732.     cmp.w        qy1,qx1
  733.     bmi.s        project_node    
  734. .x:    tst.l        d0
  735.     rts
  736. *-------------------------------------------------------*
  737. oct_7:    move.w        nodevtx_y1(a0),qy1
  738.     move.w        nodevtx_x1(a0),qx1
  739.     sub.w        d6,qy1
  740.     bpl.s        .x
  741.     sub.w        d5,qx1
  742.     neg.w        qy1
  743.     cmp.w        qy1,qx1
  744.     bmi.s        project_node
  745. .x:    tst.l        d0
  746.     rts
  747.     
  748. *~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
  749. *    Intersect node with viewcone in 2D        *
  750. *~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
  751. project_node:    
  752. *-------------------------------------------------------*
  753.     pea        (a1)
  754. *-------------------------------------------------------*
  755.     move.w        #$1000,d0
  756.     move.l        d0,display_imin(a6)
  757.     neg.l        d0
  758.     move.l        d0,display_imax(a6)
  759. *=======================================================*
  760. *    Prefetch X2,Y2 for polygon loop            *
  761. *=======================================================*
  762.     move.w        nodevtx_x1(a0),d4
  763.     move.w        nodevtx_y2(a0),d6
  764.     sub.w        display_px(a6),d4
  765.     sub.w        display_py(a6),d6
  766. *-------------------------------------------------------*
  767. *    Rotate NY & NZ into canonical VZ & VX        *
  768. *-------------------------------------------------------*
  769. *    x = (dx)*sin(a) + (dy)*cos(a)            *
  770. *    z = (dx)*cos(a) - (dy)*sin(a)            *
  771. *-------------------------------------------------------*
  772.     move.w        display_sina(a6),d1
  773.     move.w        display_cosa(a6),d2
  774.     move.w        d4,d3
  775.     move.w        d6,d5
  776.     muls.w        d2,d4
  777.     muls.w        d1,d6
  778.     muls.w        d1,d3
  779.     muls.w        d2,d5
  780.     sub.l        d6,d4
  781.     add.l        d5,d3
  782.     lsl.l        #2,d3
  783.     lsl.l        #2,d4
  784. *-------------------------------------------------------*
  785. *    Limit & hold as X2,Y2                *
  786. *-------------------------------------------------------*
  787.     move.l        d3,a2
  788.     move.l        d4,a3
  789. *=======================================================*
  790. *    2D polygon cone-intersection             *
  791. *=======================================================*
  792.     lea        nodev_indices,a1
  793.     moveq        #4-1,d7
  794. *-------------------------------------------------------*
  795. *    Fetch new X1,Y1 & centre at origin        *
  796. *-------------------------------------------------------*
  797. .rect:    move.w        (a1)+,d6
  798.     move.w        (a1)+,d2
  799.     move.w        (a0,d6.w),d6
  800.     move.w        (a0,d2.w),d2
  801.     sub.w        display_px(a6),d6
  802.     sub.w        display_py(a6),d2
  803. *-------------------------------------------------------*
  804. *    Rotate NY & NZ into canonical VZ & VX        *
  805. *-------------------------------------------------------*
  806. *    x = (dx)*sin(a) + (dy)*cos(a)            *
  807. *    z = (dx)*cos(a) - (dy)*sin(a)            *
  808. *-------------------------------------------------------*
  809.     move.w        display_sina(a6),d3
  810.     move.w        display_cosa(a6),d4
  811.     move.w        d6,d5
  812.     move.w        d2,d1
  813.     muls.w        d4,d6
  814.     muls.w        d3,d2
  815.     muls.w        d3,d5
  816.     muls.w        d4,d1
  817.     sub.l        d2,d6
  818.     add.l        d1,d5
  819.     lsl.l        #2,d5
  820.     lsl.l        #2,d6
  821. *-------------------------------------------------------*
  822. *    Clip X1,Y1 / store next X2,Y2 / get this X2,Y2    *
  823. *-------------------------------------------------------*
  824.     move.l        a2,d3
  825.     move.l        a3,d4
  826.     move.l        d5,a2
  827.     move.l        d6,a3
  828. *-------------------------------------------------------*
  829. *    Reorient line and check against viewplane    *
  830. *-------------------------------------------------------*
  831.     cmp.l        d4,d6
  832.     bpl.s        .swap
  833.     exg.l        d3,d5
  834.     exg.l        d4,d6
  835. .swap:    moveq        #ZMIN,d1
  836.     swap        d1
  837.     cmp.l        d1,d6
  838.     ble.s        .next    
  839. *-------------------------------------------------------*
  840. *    z-clip line if it intersects with viewplane    *    
  841. *-------------------------------------------------------*
  842.     moveq        #ZMIN,d0
  843.     swap        d0
  844.     sub.l        d4,d0        ; (cz-z1)
  845.     ble.s        .nzcl    
  846.     move.l        d5,d1
  847.     sub.l        d3,d1        ; (x2-x1)
  848.     muls.l        d0,d2:d1    ; (x2-x1)*(cz-z1)
  849.     move.l        d6,d0
  850.     sub.l        d4,d0        ; (z2-z1)
  851.     divs.l        d0,d2:d1    ; ((x2-x1)*(cz-z1))/(z2-z1)
  852.     add.l        d1,d3        ; (((x2-x1)*(cz-z1))/(z2-z1))+x1
  853.     moveq        #ZMIN,d4
  854.     swap        d4        ; z1 = cz
  855. *-------------------------------------------------------*
  856. *    Project points into 2D viewspace        *
  857. *-------------------------------------------------------*
  858. .nzcl:    moveq        #0,d1
  859.     move.w        display_shwid(a6),d1
  860.     muls.l        d1,d0:d3
  861.     divs.l        d4,d0:d3
  862.     muls.l        d1,d0:d5
  863.     divs.l        d6,d0:d5
  864. *-------------------------------------------------------*
  865. *    Adjust bounds                    *
  866. *-------------------------------------------------------*
  867.     move.l        display_imin(a6),d1
  868.     neg.l        d3
  869.     neg.l        d5
  870.     move.l        display_imax(a6),d2
  871.     cmp.l        d1,d3
  872.     bpl.s        .n1
  873.     move.l        d3,d1
  874. .n1:    cmp.l        d2,d3
  875.     ble.s        .n2
  876.     move.l        d3,d2
  877. .n2    cmp.l        d1,d5
  878.     bpl.s        .n3
  879.     move.l        d5,d1
  880. .n3:    cmp.l        d2,d5
  881.     ble.s        .n4
  882.     move.l        d5,d2
  883. .n4:    move.l        d1,display_imin(a6)
  884.     move.l        d2,display_imax(a6)
  885. .next:    dbra        d7,.rect
  886. *-------------------------------------------------------*
  887. *    Inside / outside viewport check            *
  888. *-------------------------------------------------------*
  889.     move.l        display_imin(a6),d3
  890.     moveq        #0,d0
  891.     move.l        display_imax(a6),d5
  892.     subq.l        #1,d3
  893.     addq.l        #1,d5
  894.     moveq        #0,d2
  895.     move.w        display_width(a6),d2
  896.     move.l        d2,d1
  897.     lsr.l        d1
  898.     add.l        d1,d5
  899.     bmi.s        .end
  900.     add.l        d1,d3
  901.     bpl.s        .x1in
  902.     moveq        #0,d3
  903. .x1in:    cmp.l        d2,d3
  904.     bpl.s        .end
  905.     cmp.l        d2,d5
  906.     bmi.s        .x2in
  907.     move.l        d2,d5
  908. .x2in:    sub.l        d3,d5
  909.     ble.s        .end
  910. *-------------------------------------------------------*
  911. *    Occlusion check                    *
  912. *-------------------------------------------------------*
  913.     ifd        dsp
  914. *-------------------------------------------------------*
  915.     add.l        d3,d5
  916.     dspwrite.l    #scan_command
  917.     dspwrite.l    d3
  918.     dspwrite.l    d5
  919.     dspread.w    d0
  920.     ext.l        d0
  921. *-------------------------------------------------------*
  922.     elseif
  923. *-------------------------------------------------------*
  924.     moveq        #1,d0
  925.     lea        occlusion_list,a2
  926.     add.w        d3,a2
  927.     moveq        #4-1,d2
  928.     and.w        d5,d2
  929.     lsr.w        #2,d5
  930.     bra.s        .sbs
  931. .sb:    tst.b        (a2)+
  932.     bne.s        .end
  933. .sbs:    dbra        d2,.sb
  934.     bra.s        .sls
  935. .sl:    tst.l        (a2)+
  936.     bne.s        .end
  937. .sls:    dbra        d5,.sl
  938.     moveq        #0,d0
  939. *-------------------------------------------------------*
  940.     endc
  941. *-------------------------------------------------------*
  942. .end:    pop.l        a1
  943. *-------------------------------------------------------*
  944. *    Return exitcode                    *
  945. *-------------------------------------------------------*
  946. end_nodecheck:
  947. *-------------------------------------------------------*
  948.     tst.l        d0
  949.     rts 
  950.  
  951. *-------------------------------------------------------*
  952.             data
  953. *-------------------------------------------------------*
  954.  
  955. *-------------------------------------------------------*
  956. *    Ordered list of node->polygon vertex defs    *
  957. *-------------------------------------------------------*
  958. nodev_indices:        dc.w    nodevtx_x1,nodevtx_y1
  959.             dc.w    nodevtx_x2,nodevtx_y1
  960.             dc.w    nodevtx_x2,nodevtx_y2
  961.             dc.w    nodevtx_x1,nodevtx_y2
  962.  
  963. *-------------------------------------------------------*
  964.             bss
  965. *-------------------------------------------------------*
  966.  
  967. maxnode:        ds.l    1    
  968. floor_ht:        ds.l    1    
  969. ceiling_ht:        ds.l    1    
  970. first_ssector:        ds.w    1    
  971. sector_colour:        ds.w    1
  972. this_sector:        ds.l    1
  973. bsp_return:        ds.l    1
  974. twosided_flag:        ds.b    1
  975.             even
  976.  
  977. *-------------------------------------------------------*
  978.             text
  979. *-------------------------------------------------------*
  980.